package Graph.Medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class LC0207 {
    /**
     * 根据题目描述，“无法修完所有课程”的情况就是一系列课程互相为先修课程，出现一个环。可以通过检查是否可以产生合法的拓扑排序，来解决这一问题。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建数据结构
        int[] inDegree = new int[numCourses];
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        for (int[] pair : prerequisites) {
            inDegree[pair[1]]++;
            adjList.get(pair[0]).add(pair[1]);
        }

        HashSet<Integer> sortedNodes = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sortedNodes.add(node);
            for (int v : adjList.get(node)) {
                inDegree[v]--;
                if (inDegree[v] == 0) queue.offer(v);
            }
        }

        return sortedNodes.size() == numCourses;
    }
}
